The present invention relates generally to communication systems for processing information, and more particularly to computer-implemented processes and systems for reliably encoding and decoding information over a communication system.
One way to enhance the reliability of a communication system transmitting an information signal is by using multiple description coding (MDC) at a source coder. MDC decomposes the information signal (i.e., input data such as a video stream or an audio stream) into subsignals called samples. Each sample can then be quantized, coded, and transmitted over the communication system in the form of coded bitstreams (referred to as descriptions), via communication channels, independent from the other samples. MDC is designed such that a reconstructed signal can be assembled from any subset of the descriptions. Thus, the reconstructed signal can be assembled with fewer than all of the descriptions. The higher the number of descriptions used in the reconstruction, the higher the quality of the reconstructed signal.
Multiple description coding was first studied from a rate-distortion theory point of view. The motivation behind MDC is to combat signal loss due to path failures. To realize this goal, each coded sample (i.e., description) carries sufficient information about the original signal. Essentially this requires a certain degree of redundancy to be embedded between the multiple descriptions. This reduces coding efficiency compared to conventional signal description coding (SDC) where there is no redundancy. As used herein, the term “coding” and “encoding” are used interchangeably.
Wolf, J. K., Wyner, A., and Ziv, 3., “Source Coding for Multiple Descriptions,” The Bell System Technical Journal, vol. 59, pp. 1417-1426, October 1980 showed that given R1 and R2 representing the bit rates for two descriptions, respectively, a total bit rate 2R, and E2 (R1, R2) representing a reconstruction error when both descriptions are received, the minimum distortion achievable by a single description coder, Emin (2R), is less than the minimal distortion achievable by a multiple description coder when both descriptions are available, E2 (R1, R2), if R1, +R2=2R. Wolf et al. showed this using a rate distortion analysis for an independent identically distributed binary source.
Ozarow, L., “On a Source Coding Problem With Two Channels and Three Receivers,” The Bell System Technical Journal Vol. 59, p. 1921, December 1980 also showed that the performance of a single description coder is better than the performance of a multiple description coder when both descriptions are available in the case of an independent identically distributed Gaussian source.
Specifically, Ozarow showed that if each coder is optimal in the rate distortion sense, i.e., E1,j (Rj) is minimized for a given Rj, then the joint coder will be far from optimal, i.e., E2 (R1, R2) is much larger than the minimal distortion achievable for this source Emin (R1+R2). The converse is also true: if the joint coder is optimal, i.e., E2 (R1, R2)≈Emin (R1+R2), then either one of the coders will be far from optimal, i.e., E1,j (R) is much larger than Emin (R) for j=1 or j=2 or both.
With real image and video signals, the redundancy in the signal (such as the correlation among adjacent samples) can help reduce the loss in coding efficiency, but a certain amount of sacrifice in coding efficiency is unavoidable. However, this reduced coding efficiency is in exchange for increased robustness to long burst errors and/or channel failures. With SDC, one would have to spend many error-control bits and/or introduce additional latency to correct such channel errors. With MDC, a long burst error or even the loss of one description does not have a catastrophic effect, as long as not all the descriptions are experiencing failures simultaneously. Thus, one could use fewer error control bits for each description. In this sense, the MDC is a way of performing joint source and channel coding.
The first practical multiple description coding was proposed for speech coding. In this approach, a bitstream from a differential pulse code modulation (DPCM) coder is split into even and odd sample packets. If an even (odd) sample packet is lost, data contained in the odd (even) sample packet are used to interpolate the missing even (odd) samples. It was shown that this coder works well beyond what the analysis predicted. This is in part because the analytical results hold true at highly efficient coders while their proposed coder is not efficient. In fact, there is sufficient redundancy left in the coder output, to permit subsampling and high quality interpolation.
In another approach to MDC, multiple descriptions are obtained by quantizing each sample using two quantizers. The quantizers are designed so that the combination of the two quantizers leads to a finer quantizer, while each quantizer itself is a coarse quantizer. The simplest implementation of this approach uses two quantizers whose decision regions shift by half of the quantizer interval with respect to each other. In this case, 2R bits are required to match the performance of a single quantizer with R+1 bits. Therefore, the loss in coding efficiency is quite significant, for the value of R being relatively high. Although more sophisticated quantizer mappings can be designed to improve the coding efficiency, a direct application of this approach to the original samples of a signal is not advisable in terms of loss in coding efficiency. Recently, this approach has been applied to transform coefficients in transform coders, with applications in speech, image, and video. The loss in coding efficiency is less severe in this case, but still quite high, up to 30%.
While offering a good redundancy rate distortion performance at low redundancies, a serious drawback of the two sample transform-based MDC methods is that they fail to reduce one-channel distortion to levels close to two-channel distortion with high redundancies (i.e., near half the total bit rate). This is due to the fact that the two sample transform-based MDC sends one variable on each channel, regardless of the redundancy.
The present invention is therefore directed to the problem of developing a method and apparatus for performing multiple description coding that improves the coding efficiency for a two sample transform.